/* 
 * File:   graph.h
 * Author: emi
 *
 * Created on 4 de febrero de 2014, 07:20 PM
 */

#ifndef GRAPH_H
#define	GRAPH_H

#include <iostream>
#include <list>
#include <string>

#ifdef	__cplusplus
extern "C" {
#endif



using namespace std;

class Path{

public:

  list<int> * path;

  // Constructors
  Path();
  Path(Path * p);

  // Methods
  bool IsEmpty();
  void Replace(Path * p, int u, int v); // sustituye el subcamino de u a v en this por p, u y v estan contenidos en this
  	  	  	  	  	  	  	  	  	  	  // y en p (p es un camino que une los nodos u y v)
  Path* SubPath(int i, int j); // retorna un nuevo camino, subcamino de p, de inicio i y fin j.
  bool Contains(Path* p); // retorna true si contengo el camino p
  bool Contains(int node); // retorna true si contengo el nodo en el camino
  bool Contains(pair<int,int> * edge); // retorna true si contiene la arista (a ,b)
  int Length(); // cantidad de nodos en el camino
  int& operator[](int x);

  int Size();

  ~Path();


};



class PathMatrix{

public:

  list<Path*> * ** P;
  int sizeP;

  // Constructors
  PathMatrix();
  PathMatrix(int size);
  PathMatrix(PathMatrix * _PM);

  bool IsNodeDisjointTo(Path* p , int i, int j); // retorna true si no hay otro camino de i a j con los nodos del camino p, sin incluir i,j
  void Add(Path* p, int i, int k) ; // agrega el camino a la matriz.
  void Update(Path* p_old, Path* p_new); // all camino que contenga a p_old se le sustituye p_old por p_new, p_new y p_old
  	  	  	  	  	  	  	  	  	  	 // comparten extremos (son caminos que unenen un mismo par de nodos)
  bool Contains(Path * p, int i, int j); // retorna el camino en P[i][j] que contiene a p, en otro caso NULL (solo puede existir uno son nodos disjuntos)
  list<Path*> **& operator[](int x);

  ~PathMatrix();
};


class Graph {

public:

    int sizeG;	// Size del grafo

    int ** C;	// Costo de las aristas
    int * W;	// Costo de los nodos


    int ** E;	// Aristas propiamente dicho, pasa que las aristas pueden tener costo cero y aun asi la arista existe.
    			// Si E[i][i]==1 la arita (i, j) exite y su costo es C[i][j]

    int ** R;	// Requerimientos de conectividad no satisfechos

    list<int> * T;	// Nodos terminales
    int * _T;  // Si _T[i]==1 entonces i es terminal o(1)

    int diameter; // Diametro del problema
    int * actived_node; // Nodos activados para su uso en el grafo

    Graph(); // constructor por defecto, no pide memoria para las estructuras internas
    Graph(int sizeG); /// solo allocate memoria, all inizializado en cero
    Graph(const char* file_path); // carga desde archivo
    Graph(Graph* G); // copia
    
    void agregarArista(int origen, int destino, int costo);

    void Add(Path* p);  //agrega el camino al grafo habilitando nodos y aristas, efectua el cambio sobre this
    void Add(list<int>* p);  //agrega el camino al grafo habilitando nodos y aristas, efectua el cambio sobre this
    void Add(list<list<int>*>* lista_p);  //agrega el camino al grafo habilitando nodos y aristas, efectua el cambio sobre this
    
    void Substract(Path * p); // elimina del grafo todos los nodos y aristas que pertenecen al camino, efectua el cambio sobre this..... eliminacion virual desactiva los nodos y aristas
    void SubstractWithoutExtremes(Path * p); // elimina del grafo todos los nodos y aristas que pertenecen al camino excepto los extremos, efectua el cambio sobre this..... eliminacion virual desactiva los nodos y aristas
    
    void Substract(list<int> * p); // elimina del grafo todos los nodos y aristas que pertenecen al camino, efectua el cambio sobre this..... eliminacion virual desactiva los nodos y aristas
    void SubstractWithoutExtremes(list<int> * p); // elimina del grafo todos los nodos y aristas que pertenecen al camino excepto los extremos, efectua el cambio sobre this..... eliminacion virual desactiva los nodos y aristas    
    
    void Substract(list<Path*> * paths); // para cada camino: elimina del grafo todos los nodos que pertenecen al camino, efectua el cambio sobre this..... eliminacion virual desactiva los nodos
    void SubstractWithoutExtremes(list<Path*> * paths); // para cada camino: elimina del grafo todos los nodos que pertenecen al camino, excepto los extremos.
    
    void Substract(list<list<int>*> * paths); // para cada camino: elimina del grafo todos los nodos que pertenecen al camino, efectua el cambio sobre this..... eliminacion virual desactiva los nodos
    void SubstractWithoutExtremes(list<list<int>*> * paths); // para cada camino: elimina del grafo todos los nodos que pertenecen al camino, excepto los extremos.

    list<Path*> * KeyPathDescomposition(); // calcula la descomposicion en key-path del grafo.
    list<Path*> * GetKPathsBetween(int src, int dst, int k, int l); // retorna hasta k caminos entre src y dst , con maximo diametro l (no tienen por que ser nodo disjuntos)

    int GetNodeGrade(int node);
    bool IsTerminal(int node);
    list<int> * GetNeighbors(int node);
    list<int> * GetNeighbors(int node, list<int> * candidates); // retorna todos los vecinos de "node" que se encuntran en la lista "candidates"
    int Cost();

    int CostPath(Path * p); // retorna el costo del camino p segun su matrices de costo C y W, se supone que p esta en el grafo
    int CostListInt(list<int> * l); // retorna el costo del camino p segun su matrices de costo C y W, se supone que p esta en el grafo

    void Dump(char * file_path);
    
    list<int>* getKeyNodes();
    
    /**
     * Retorna una lista con lista de nodos, en cada una de estas listas en front esta el nodo raiz y en back las hojas
     * @param v
     * @return 
     */
    list<list<int>*>* getKeyTree(int v);
    
    list<int>* auxHojasKTree(list<list<int>*>*);
    list<int>* auxNodosSteinerKTree(list<list<int>*>*);
    
    //Graph* subGrafoInducidoMasAristas(list<int>* conjNodos, list<pair<int, int>*>* Aw);
    //Graph* subGrafoInducidoMasAristas(v,Zv,Sv,Stecho,Aw);
    Graph* subGrafoInducidoMasAristas(list<int>* conjNodos,list<int>* Zv);

    bool esFactible();
    
    list<list<int>*>* caminoNodoDisjuntos(int source, int dest);
    
    void graph_viz(const char* rutaSalida, const char* nombreGrafo);
    void imprimirLista(list<int>* L, const char* mensaje) ;
    void imprimirKtree(list<list<int>*>* kTree, const char* mensaje) ;
    
    void sub_graph_viz(Graph* H, const char* rutaSalida, const char* nombreGrafo);
    void subLista_graph_viz(list<Path*>* LP, int o, int d, const char* nombreGrafo);
    ~Graph(); //

};

#ifdef	__cplusplus
}
#endif

#endif	/* GRAPH_H */

